package LearnAlgorithm.d_标准查找算法and标准排序算法;


public class b3插入排序 {
	public static void main(String[] args) {
		int[] arr = new int[] {6,8,7,9,5,4,3,6};
		insertSort(arr);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	/**
	 * 插入排序
	 * O(N^2)
	 * @param arr
	 * @param p
	 * @param r
	 */
	public static void insertSort(int[] arr, int p, int r) {//对数组自定义片段进行排序
		int value_i = 0;
		int before_i = 0;
		for (int i = p + 1; i <= r; i++) {//这里int i = p + 1;可以写成int i = p;但是从p开始第一次循环肯定是判断不通过的，为了改进性能(即便这个性能提升很微弱)就从p+1开始了
			value_i = arr[i];
			before_i = i - 1;
			while (before_i > p - 1 && arr[before_i] > value_i) {
				arr[before_i + 1] = arr[before_i];
				before_i--;
			}
			arr[before_i + 1] = value_i;
		}
	}
	
	public static void insertSort(int[] arr) {//对数组全部数据进行排序
		int value_i = 0;
		int before_i = 0;
		for (int i = 1; i < arr.length; i++) {//这里int i = 1;可以写成int i = 0;但是从0开始第一次循环肯定是判断不通过的，为了改进性能(即便这个性能提升很微弱)就从1开始了
			value_i = arr[i];//不能删除此行；此行在交换前把arr[i]的值保存在value_i中
			before_i = i - 1;
			while (before_i > -1 && arr[before_i] > value_i) {
				arr[before_i + 1] = arr[before_i];
				before_i--;
			}
			arr[before_i + 1] = value_i;//在交换后，再把这个值赋给目标位置
		}
	}
}
